2018/5/30

Background Removal with Robust PCA

Unit 3 Lecture 4

SVD:

• Singular Value Decomposition: 1st matrix of orthonormal columns, 2nd a diagonal matrix with singular values in descending order, and 3rd a matrix of orthonormal rows.

Randomized SVD:

• Trying to get truncated form much faster. Full SVD: able to fully reconstruct data matrix. May be useful, but unnecessary & pot.harmful for data-compression or focus on speed. Quicker to not calculate everything.

Full SVD is slow. Randomized SVD much faster (pot.by an order of magnitude).

SVD runtime complexity: O(min(m$^2$n, mn$^2$))

Instead of calculating SVD on full matrix A (size: (m,n)), use B = AQ of size (m,r) where r << n.

We end up using the same scipy implementation of SVD, but we just multiply our matrix by a random one to make it smaller. B is a low-rank approximation of A, given that it needs to have the same or similar column space to work well.